// 给定一个二叉树，找出其最小深度
// 最小深度是从根节点到最近叶子节点的最短路径上的节点数量
// 思路1，层序遍历
function minDepth(root) {
    let queue = []
    let minHeight = 0
    if (root) {
        queue.push(root)
    }
    while (queue.length) {
        let len = queue.length
        minHeight++
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            // 找到第一个叶子节点
            if (!node.left && !node.right) {
                return minHeight
            }
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return minHeight
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
    },
};

console.log(minDepth(root));

// 思路2， 递归
function minDepth2(root) {
    if (!root) {
        return 0
    }
    if (!root.left && !root.right) {
        return 1
    }
    // 小心，当left没有的时候，当right没有的时候，得从另一个子节点查找，小心漏掉
    if (!root.left) {
        return minDepth2(root.right) + 1
    }
    if (!root.right) {
        return minDepth2(root.left) + 1
    }
    return Math.min(minDepth2(root.left), minDepth2(root.right)) + 1
}

console.log(minDepth2(root));